// 7.1　没有优化的并查集
// class UnionFind {
//     constructor(size) {
//       this.size = size; // 表示当前还有多少个小组
//       this.parents = new Array(size);
//       for (var i = 0; i < size; i++) {
//         this.parents[i] = i;
//       }
//     }
//     // 查看元素属于哪个集合
//     query(element) {
//       return this.parents[element];
//     }
    
//     // 合并a、b所在的集合
//     merge(a, b) {
//       var p1 = this.query(a);
//       var p2 = this.query(b);
//       // 如果这两个元素不是同一个集合，那么合并
//       if (p1 !== p2) {
//         this.size--;
//         // 遍历数组，使原来的p1、p2合并为p2
//         for (var i = 0; i < this.size; i++) {
//           if (this.parents[i] === p1) {
//             this.parents[i] = p2;
//           }
//         }
//       }
//     }
//     // 查看元素a、b是否在同一个集合，如果不在，那么合并（有专门的术语叫连接）
//     isConnected(a, b) {
//       return this.query(a) === this.query(b);
//     }
//     toString() {
//       return this.parents.join(" ");
//     }
//   }
//   var union = new UnionFind(10);
//   console.log("初始化");
//   console.log(union + "");
  
//   console.log("连接了5 6");
//   union.merge(5, 6);
//   console.log(union + "");
  
//   console.log("连接了1 2");
//   union.merge(1, 2);
//   console.log(union + "");
  
//   console.log("连接了2 3");
//   union.merge(2, 3);
//   console.log(union + "");
  
//   console.log("连接了1 4");
//   union.merge(1, 4);
//   console.log(union + "");
  
//   console.log("连接了1 5");
//   union.merge(1, 5);
//   console.log(union + "");
  
//   console.log("1  6 是否连接：" + union.isConnected(1, 6));
//   console.log("1  8 是否连接：" + union.isConnected(1, 8));
//   7.2　快速合并，慢查找

// class UnionFind {
//     constructor(size) {
//       this.size = size; // 表示当前还有多少个小组
//       this.parents = new Array(size);
//       for (var i = 0; i < size; i++) {
//         this.parents[i] = i;
//       }
//     }
//     // 查看元素属于哪个集合
//     query(element) {// 只上报最终BOSS的组名
//       var p = this.parents;
//       while (element !== p[element]) { // 一样，说明到顶，否则往上找
//         element = p[element];
//       }
//       return element;
//     }
   
//     // 合并元素a、b所在的集合
//     merge(a, b) {
//       var p1 = this.query(a);
//       var p2 = this.query(b);
//       // 如果这两个元素不是同一个集合，那么将其中一个“老大”的值改写为另一个“老大”的值
//       if (p1 !== p2) {
//         this.size--;
//         this.parents[p1] = p2;
//       }
//     }
//     // 查看元素a、b是否在同一个集合，如果不在，那么合并（有专门的术语叫连接）
//     isConnected(a, b) {
//       return this.query(a) === this.query(b);
//     }
//     toString() {
//       return this.parents.join(" ");
//     }
//   }
//   var union = new UnionFind(10);
//   console.log("初始化");
//   console.log(union + "");
  
//   console.log("连接了5 6");
//   union.merge(5, 6);
//   console.log(union + "");
  
//   console.log("连接了1 2");
//   union.merge(1, 2);
//   console.log(union + "");
  
//   console.log("连接了2 3");
//   union.merge(2, 3);
//   console.log(union + "");
  
//   console.log("连接了1 4");
//   union.merge(1, 4);
//   console.log(union + "");
  
//   console.log("连接了1 5");
//   union.merge(1, 5);
//   console.log(union + "");
  
//   console.log("1  6 是否连接：" + union.isConnected(1, 6));
  
//   console.log("1  8 是否连接：" + union.isConnected(1, 8));

//   7.3　基于权重的快速合并，快速查找

// class UnionFind {
//     constructor(size) {
//       this.size = size; // 表示当前还有多少个小组
//       this.parents = new Array(size);
//       this.weights = new Array(size);
//       for (var i = 0; i < size; i++) {
//         this.parents[i] = i;
//         this.weights[i] = 1; // 每一个集合只有一个元素
//       }
//     }
//     // 查看元素属于哪个集合
//     query(element) {
//       var p = this.parents;
//       while (element !== p[element]) { // 如果一样，就到顶，否则继续往上找
//         element = p[element];
//       }
//       return element;
//     }
//     // 合并元素a、b所在的集合
//     merge(a, b) {
//       var p1 = this.query(a);
//       var p2 = this.query(b);
//       // 如果这两个元素不是同一个集合，那么将其中一个“老大”的值改写为另一个“老大”的值
//       if (p1 !== p2) {
//         this.size--;
//         if (this.weights[p1] > this.weights[p2]) {
//           this.parents[p2] = p1;
//           this.weights[p1] += this.weights[p2];
//         } else {
//           this.parents[p1] = p2;
//           this.weights[p2] += this.weights[p1];
//         }
//       }
//     }
//     // 查看元素a、b是否在同一个集合
//     isConnected(a, b) {
//         return this.query(a) === this.query(b);
//       }
//       toString() {
//         return this.parents.join(" ");
//     }
//   }
//   var union = new UnionFind(10);
//   console.log("初始化");
//   console.log(union + "");
  
//   console.log("连接了5 6");
//   union.merge(5, 6);
//   console.log(union + "");
  
//   console.log("连接了1 2");
//   union.merge(1, 2);
//   console.log(union + "");
  
//   console.log("连接了2 3");
//   union.merge(2, 3);
//   console.log(union + "");
  
//   console.log("连接了1 4");
//   union.merge(1, 4);
//   console.log(union + "");
  
//   console.log("连接了1 5");
//   union.merge(1, 5);
//   console.log(union + "");
  
//   console.log("1  6 是否连接：" + union.isConnected(1, 6));
  
//   console.log("1  8 是否连接：" + union.isConnected(1, 8));


// 7.4　基于深度的快速合并，快速查找
// class UnionFind {
//     constructor(size) {
//        this.size = size; // 表示当前还有多少个小组
//        this.parents = new Array(size);
//        this.depth = new Array(size);
//        for (var i = 0; i < size; i++) {
//          this.parents[i] = i;
//          this.depth[i] = 1;
//        }
//      }
//      // 查看元素属于哪个集合
//      query(element) {
//        var p = this.parents;
//        while (element !== p[element]) {// 如果一样，就到顶，否则继续往上找
//          element = p[element];
//        }
//        return element;
//      }
//      // 合并a、b所在的集合
//      merge(a, b) {
//        var p1 = this.query(a);
//        var p2 = this.query(b);
//        // 如果这两个元素不是同一个集合，那么将其中一个“老大”的值改写为另一个“老大”的值
//        if (p1 !== p2) {
//          this.size--;
//          if (this.depth[p1] > this.depth[p2]) {
//            this.parents[p2] = p1;
//          } else if (this.depth[p2] > this.depth[p1]) {
//            this.parents[p1] = p2;
//          } else {
//            this.parents[p1] = p2;
//            this.depth[p2] += 1;
//          }
//        }
//      }
//      // 查看元素a、b是否在同一个集合
//      isConnected(a, b) {
//         return this.query(a) === this.query(b);
//       }
//       toString() {
//         return this.parents.join(" ");
//     }
//    }
//    var union = new UnionFind(10);
//    console.log("初始化");
//    console.log(union + "");

//    console.log("连接了5 6");
//    union.merge(5, 6);
//    console.log(union + "");

//    console.log("连接了1 2");
//    union.merge(1, 2);
//    console.log(union + "");

//    console.log("连接了2 3");
//    union.merge(2, 3);
//    console.log(union + "");

//    console.log("连接了1 4");
//    union.merge(1, 4);
//    console.log(union + "");

//    console.log("连接了1 5");
//    union.merge(1, 5);
//    console.log(union + "");

//    console.log("1  6 是否连接：" + union.isConnected(1, 6));

//    console.log("1  8 是否连接：" + union.isConnected(1, 8));

// 7.5　基于权重与路径压缩的快速合并，快速查找

class UnionFind {
    constructor(size) {
      this.size = size; // 表示当前还有多少个小组
      this.parents = new Array(size);
      this.weights = new Array(size);
      for (var i = 0; i < size; i++) {
        this.parents[i] = i;
        this.weights[i] = 1;
      }
    }
    // 查看元素属于哪个集合
    query(element) {
      var p = this.parents;
      while (element !== p[element]) { // 如果一样，就到顶，否则继续往上找
        p[element] = p[p[element]];
        element = p[element];
      }
      return element;
    }
    // 合并元素a、b所在的集合
    merge(a, b) {
      var p1 = this.query(a);
      var p2 = this.query(b);
      // 如果这两个元素不是同一个集合，那么将其中一个“老大”的值改写为另一个“老大”的值
      if (p1 !== p2) {
        this.size--;
        if (this.weights[p1] > this.weights[p2]) {
          this.parents[p2] = p1;
          this.weights[p1] += this.weights[p2];
        } else {
          this.parents[p1] = p2;
          this.weights[p2] += this.weights[p1];
        }
      }
    }
    // 查看元素a、b是否在同一个集合
     isConnected(a, b) {
        return this.query(a) === this.query(b);
      }
      toString() {
        return this.parents.join(" ");
    }
  }
//   var union = new UnionFind(10);
//   console.log("初始化");
//   console.log(union + "");
  
//   console.log("连接了5 6");
//   union.merge(5, 6);
//   console.log(union + "");
//   console.log("连接了5 6 之后的weights：");
//   console.log(union.weights);
  
//   console.log("连接了1 2");
//   union.merge(1, 2);
//   console.log(union + "");
//   console.log("连接了1 2 之后的weights：");
//   console.log(union.weights);
  
//   console.log("连接了2 3");
//   union.merge(2, 3);
//   console.log(union + "");
//   console.log("连接了2 3 之后的weights：");
//   console.log(union.weights);
  
//   console.log("连接了1 4");
//   union.merge(1, 4);
//   console.log(union + "");
//   console.log("连接了1 4 之后的weights：");
//   console.log(union.weights);
  
//   console.log("连接了1 5");
//   union.merge(1, 5);
//   console.log(union + "");
//   console.log("连接了1 5 之后的weights：");
//   console.log(union.weights);
  
//   console.log("1  6 是否连接：" + union.isConnected(1, 6));
  
//   console.log("1  8 是否连接：" + union.isConnected(1, 8));


// 7.6　相关问题
// 7.6.1　朋友圈
// class UnionFind{ 
//     // 直接借鉴上面最后一种实现
//   }
//   function findCircleNum(matrix) {
//     var union = new UnionFind(matrix.length);
//     for(var i = 0; i < matrix.length; i++){
//       var row = matrix[i];
//       for(var j = 0; j < row.length; j++){
//         if(matrix[i][j] === 1){
//           union.merge(i, j );
//         }
//       }
//     }
//     return union.size;
//   }
  
//   console.log(findCircleNum( [[1,1,0],[1,1,0],[0,0,1]])); // 2
//   console.log(findCircleNum( [[1,1,0],[1,1,1],[0,1,1]])); // 1

//   7.6.2　岛屿的数量
// function numIslands(grid) {
//     var size = 0,total = 0;
//     for (var i = 0; i < grid.length; i++) {
//       var row = grid[i];
//       for (var j = 0; j < row.length; j++) {
//         if (row[j] === '1') {
//           size++;
//         }
//         total ++;
//       }
//     }
//     var union = new UnionFind(total);
//     union.size = size;
//     for (var i = 0; i < grid.length; i++) {
//       var row = grid[i];
//       var topRow = grid[i - 1];// 上面一行
//       var n = row.length;
//       for (var j = 0; j < n; j++) {
//         if (row[j] === '1' && row[j + 1] === '1') {
//           union.merge(i * n + j, i * n + j + 1); // 左右相邻，合并
//         }
//         if (topRow && row[j] === '1'  && topRow[j] === '1') {
//           union.merge(i * n + j, (i - 1) * n + j);// 上下相邻，合并
//         }
//       }
//     }
//     return union.size;
// }
// console.log(numIslands([
//     ['1','1','0','0','0'],
//     ['1','1','0','0','0'],
//     ['0','0','1','0','0'],
//     ['0','0','0','1','1']
// ]));

// 7.6.3　账户合并
// function accountsMerge(accounts) {
//     var union = new UnionFind(accounts.length);
//     var owners = {};
//     // 开始合并账户
//     for (var i = 0; i < accounts.length; i++) {
//       var emails = accounts[i];
//       for (var j = 1; j < emails.length; j++) {
//         var email = emails[j];
//         if (owners.hasOwnProperty(email)) {
//           var person = owners[email];
//           union.merge(i, person); // 如果共用一个邮箱，说明是同一个人，合并
//         } else {
//           owners[email] = i;
//         }
//       }
//     }
//     // 提取用户对应的邮件
//     var userEmails = {};
//     for (var i = 0; i < accounts.length; i++) {
//       var rootIndex = union.query(i);// 找到合并后的小组的索引值名
//       var emails = accounts[i];
//       if (!userEmails[rootIndex]) {
//         userEmails[rootIndex] = new Set();
//       }
//       emails.forEach((a, i) => {
//         if (i) {
//           userEmails[rootIndex].add(a);
//         }
//       });
//     }
//     var result = [];
//     for (var i in userEmails) {
//         var name = accounts[i][0];
//         var emails = Array.from(userEmails[i]).sort();
//         emails.unshift(name);
//         result.push(emails);
//     }
//     return result;
//   }

//  const accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]];
//  console.log(accountsMerge(accounts));


// 7.6.4　团伙问题
// function getGangs(n, counts, descriptions) {
//     var union = new UnionFind(n * 2);// 放大两倍
//     var result = 0;
//     for (var i = 0; i < counts; i++) {
//       var [type, a, b] = descriptions[i];
//       if (type === 'E') {
//         union.merge(a, b);
//       } else {
//         union.merge(a, b + n);// a与b的敌人是同伙
//         union.merge(a + n, b);// a的敌人与b是同伙
//       }
//     }
//     return union.size / 2;
//   }
//   var descriptions = [['E', 1, 4],
//     ['F', 3, 5],
//     ['F', 4, 6],
//     ['E', 1, 2]];
  
//   console.log(getGangs(6, 4, descriptions));

// 7.6.5　食物链
function getLies(n, counts, descriptions) {
    var union = new UnionFind(n * 3);
    var result = 0;
    // 总共三种物种
    for (var i = 0; i < counts; i++) {
      var [type, a, b] = descriptions[i];
      if (a === b && type === 2) {// 如果它们是同类，但又互相捕食，那就是假话
        result++;
      } else if (a > n || b > n) {// a或b比N大，就是假话
        result++;
      } else {
        if (type === 1) { // 假定这是真话，a、b是同一物种
          // a与它的天敌是同名，或a与它的食物是同名
          if (union.isConnected(a + n, b) || union.isConnected(a + 2 * n, b)) {
            result++;
          } else {
            union.merge(a, b);// 如果a、b是同类
            union.merge(a + n, b + n);// 那么它们的食物也是同类
            union.merge(a + 2 * n, b + 2 * n);// 那么它们的天敌也是同类
          }
        } else {// type == 2 假定这是真话，a、b是不同物种
          // a与b是同种，a与它的天敌是同种
          if (union.isConnected(a, b) || union.isConnected(a, b + 2 * n)) {
            result++;
          } else {
            union.merge(a + 2 * n, b);// a的天敌与b的食物是同种
            union.merge(a + n, b + 2 * n);// a的食物与b的天敌是同种
            union.merge(a, b + n);// a与b的食物是同种
          }
        }
      }
    }
    return result;
  }
  var descriptions = [
      [1,101,1], 
      [2, 1, 2],
      [2, 2, 3],
      [2, 3, 3],
      [1, 1, 3],
      [2, 3, 1],
      [1, 5, 5],
  ];
  console.log(getLies(100, 7, descriptions));